{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "A MDP is a reinterpretation of Markov chains which includes an agent and a decision making process. A MDP is defined by these components:\n",
    "1. Set of possible States: S={s0,s1,...,sm}\n",
    "2. Initial State:s0\n",
    "3. Set of possible Actions:A={a0,a1,...,an}\n",
    "4. Transition Model:T(s,a,s′)\n",
    "5. Reward Function: R(s)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We are going to implement MDP in a grid world of 3 x 4 space where our agent/robot is situated at (1,1) in the beginning and needs to reach (3,4) state which is its desired goal state. There is also a fault state at (2,4) which the robot needs to avoid at all costs. The movement of the robot from one state to another earns it a reward. Naturally, the reward for the goal state is the highest and the least for the fault state. The objective of the robot is to maximize its reward and thus plan its movements/actions accordingly. It can move in any direction and this is a stochastic process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To compare the states, we calculate the utility of these states and this is shown below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def state_utility(v, T, u, reward, gamma):\n",
    "    \n",
    "    #v is the state vector\n",
    "    #T is the transition matrix\n",
    "    #u is the utility vector\n",
    "    #reward consists of the rewards earned for moving to a particular state\n",
    "    #gamma is the discount factor by which rewards are discounted over the time\n",
    "\n",
    "    action_array = np.zeros(4)\n",
    "    for action in range(0, 4):\n",
    "        action_array[action] = np.sum(np.multiply(u, np.dot(v, T[:,:,action])))\n",
    "    return reward + gamma * np.max(action_array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Utility of state (1,1): 0.7056\n"
     ]
    }
   ],
   "source": [
    "def main():\n",
    "    \n",
    "    #The agent starts from (1, 1)\n",
    "    v = np.array([[0.0, 0.0, 0.0, 0.0, \n",
    "                   0.0, 0.0, 0.0, 0.0, \n",
    "                   1.0, 0.0, 0.0, 0.0]])\n",
    "    \n",
    "    #file loaded from the folder\n",
    "    T = np.load(\"T.npy\")\n",
    "\n",
    "    #Utility vector\n",
    "    u = np.array([[0.812, 0.868, 0.918,   1.0,\n",
    "                   0.762,   0.0, 0.660,  -1.0,\n",
    "                   0.705, 0.655, 0.611, 0.388]])\n",
    "\n",
    "    #Define the reward for state (1,1)\n",
    "    reward = -0.04\n",
    "    #Assume that the discount factor is equal to 1.0\n",
    "    gamma = 1.0\n",
    "\n",
    "    #Use the Bellman equation to find the utility of state (1,1)\n",
    "    utility_11 = state_utility(v, T, u, reward, gamma)\n",
    "    print(\"Utility of state (1,1): \" + str(utility_11))\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    main()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
